Optimizing my Ford-Fulkerson implementation for sparse graphs.
[and.git] / 10193 - All you need is love / p10193.cpp
blob79db4fdccee11fcc574c37fec822e1986ddefa41
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
5 inline unsigned long b2d(string &s){
6 reverse(s.begin(), s.end());
7 unsigned long r = 0;
8 unsigned long pow2 = 1;
9 for (int i=0; i<s.size(); ++i){
10 if (s[i] == '1')
11 r += pow2;
12 pow2 *= 2;
14 return r;
17 int gcd_short( int a, int b ) { return b ? gcd_short( b, a % b ) : a; }
19 unsigned long gcd(unsigned long a, unsigned long b){
20 unsigned long x = a, y = b, r;
21 while (y != 0){
22 r = x % y;
23 x = y;
24 y = r;
26 return x;
29 int main(){
30 int n;
31 cin >> n;
32 for (int i=1; i<=n; ++i){
33 string s,t;
34 cin >> s >> t;
35 unsigned long x = b2d(s), y = b2d(t);
36 cout << "Pair #" << i << ": ";
37 if (gcd(x,y) > 1)
38 cout << "All you need is love!";
39 else
40 cout << "Love is not all you need!";
41 cout << endl;
44 return 0;